package paixu;

/**
 * @author lj
 * @Description: 折半插入排序
 * @date 2020-10-21 22:16
 * @QQ 851477108
 */


public class ChaR2fen {

    public static void main(String[] args) {
        int[] arr = {5,8,6,2,4,3};
        int[] sort = sort(arr);
        for (int i : sort) {
            System.out.print(i+",");
        }
    }


    public static int[] sort(int[] arr){

        //如果传入的数组为空或者只有一个值,就直接返回
        if (arr == null||arr.length <= 1){
            return arr;
        }
        //不为空则进循环判断
        // 外层循环控制总数量,  //默认构造从左→右依次递增的序列
        for (int i = 1; i < arr.length; i++) {
            // 通过二分查找找到插入的位置
            int insert = findInsert(arr,0,i-1,i,arr[i]);
            // 当 insert_index = -1 时，不必做插入操作
            if (insert != -1){
                // 一下是插入排序
                int temp = arr[i];
                int j = i - 1;
                while (j >= insert){
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j+1] = temp;
            }
        }

        return arr;
    }

    /**
     * 在有序数组 nums 的[L, R]部分上，找到 value 的插入位置
     * @param arr
     * @param L
     * @param R
     * @param i
     * @param value
     * @return
     */
    private static int findInsert(int[] arr, int L, int R, int i, int value) {
        while (L <= R){
            int mid = L + ((R - L)/2);
            if (value > arr[mid]){
                L = mid + 1;
            }else {
                R = mid - 1;
            }
        }
        // 当 left >= n 时，则说明预插入数与其之前的有序序列
        // 已经形成有序序列了，因此不需要做插入操作
        if (L >= i) return -1;
        return L;
    }
}
